home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / MacDoc93+ / prof-test < prev   
Encoding:
Text File  |  1993-08-12  |  1.6 KB  |  60 lines  |  [TEXT/NJML]
  1. (*
  2. System.Directory.cd "../tools/prof/";
  3. use "e_profile_temp";
  4. *)
  5.  
  6. signature SORT =
  7.   sig
  8.     (* pass the gt predicate as an argument *)
  9.      val sort : ('a * 'a -> bool) -> 'a list -> 'a list  
  10.      val sorted : ('a * 'a -> bool) -> 'a list -> bool  
  11.      val makelist : int * int list -> int list
  12.   end
  13.  
  14. structure Sort : SORT = struct
  15.  
  16. (* smooth applicative merge sort
  17.  * Taken from, ML for the Working Programmer, LCPaulson. pg 99-100
  18.  *)
  19. fun sort (op > : 'a * 'a -> bool) ls = 
  20.     let fun merge([],ys) = ys
  21.           | merge(xs,[]) = xs
  22.           | merge(x::xs,y::ys) = 
  23.             if x > y then y::merge(x::xs,ys) else x::merge(xs,y::ys)
  24.         fun mergepairs(ls as [l], k) = ls
  25.           | mergepairs(l1::l2::ls,k) = 
  26.             if k mod 2 = 1 then l1::l2::ls
  27.             else mergepairs(merge(l1,l2)::ls, k div 2)
  28.         fun nextrun(run,[])    = (rev run,[])
  29.           | nextrun(run,x::xs) = if x > hd run then nextrun(x::run,xs)
  30.                                  else (rev run,x::xs)
  31.         fun samsorting([], ls, k)    = hd(mergepairs(ls,0))
  32.           | samsorting(x::xs, ls, k) = 
  33.             let val (run,tail) = nextrun([x],xs)
  34.             in samsorting(tail, mergepairs(run::ls,k+1), k+1)
  35.             end
  36.     in case ls of [] => [] | _ => samsorting(ls, [], 0)
  37.     end
  38.  
  39. fun sorted (op >) =
  40.   let fun s (x::(rest as (y::_))) = not(x>y) andalso s rest
  41.         | s l = true
  42.   in s
  43.   end
  44.  
  45. fun makelist (i,ls) =
  46.   let fun m (0,ls) = ls
  47.         | m (i,ls) = m(i-1,i::ls)
  48.   in m(i,ls)
  49.   end
  50.  
  51. end;
  52.  
  53. !Profile.profiling;
  54.  
  55. Profile.profileOn();
  56. Sort.sort (op <) (Sort.makelist (20000,nil));
  57. Profile.profileOff();
  58.  
  59. Profile.report std_out;
  60.